/**
 * @file src/search/AStar.java
 */
package search;

/** imports */
import datatypes.Edge;
import datatypes.Heuristics;
import datatypes.Node;
import datatypes.Path;
import datatypes.Tuple;
import datatypes.UndirectedGraph;
import java.util.Collections;
import java.util.Vector;

/**
 * AStar class
 */
public class AStar
{

	/**
	 * Search method for AStar
	 *
	 * @param graph A given problem/graph
	 * @param heur A given heuristic
	 * @param source A given source state
	 * @param a given goal state
	 * 
	 * @return Path in form of a Vector<Node> (null if there is no solution)
	 */
	public static Vector<Path> search(UndirectedGraph graph, Heuristics heur, String source, String goal) throws Exception
	{
		/** check if source and goal existent */
		Node sourceNode = graph.findNode(source);
		Node goalNode = graph.findNode(goal);
		if (sourceNode == null || goalNode == null) { throw new Exception("AStar::search() : Source or Goal not existent!"); }
		
		/** set goal for heuristics, this just ensures that there is a goal with heuristic distance 0.0f within the heuristic */
		heur.setGoal(goal);
		
		/** initialize problem */
		graph.init(source, goal);

		/** set estimated distance for source */
		sourceNode.setF(sourceNode.getPathCost() + heur.get(source));
		
		/** fringe */
		Vector<Path> fringe = new Vector<Path>();
		
		Path initialPath = new Path();
		initialPath.append(new Node(sourceNode));

		/** add initial path to fringe */
		fringe.addElement(initialPath);
		
		while (true) {
			
			/** if fringe is empty, return solution */
			if (fringe.size() == 0) {
				/** return empty solution */
				return fringe; 
			}
			
			/**
			 * Sort fringe according to the nodes' f values
			 * Path.compareTo() is overwritten 
			 */
			Collections.sort(fringe);
			
			/** get first path */
			Path parentPath = fringe.get(0);
			
			/** goal test */
			if (parentPath.getLast().getState().compareTo(goal) == 0){
				/** return fringe */
				return fringe;
			}
			
			/** remove-first from fringe */
			fringe.remove(parentPath);

			/** add its children to fringe */
			for (Tuple<Edge, Node> t: graph.getSuccessors(parentPath.getLast())) {
				
				/** copy of current child */
				Node child = new Node(t.second);
				
				/** skip if child is already existent in path */
				if (parentPath.contains(child)) { continue; }
					
				/** corresponding edge */
				Edge edge = t.first;
				
				/**  first: update path costs */
				child.setPathCost(parentPath.getCosts() + edge.getStepCost());
				
				/** second: update f value */
				child.setF(child.getPathCost() + heur.get(child.getState()));
				
				/** generate a new path for each child, respectively */
				/** the copy is essential here !!! */
				Path childPath = new Path(parentPath);
				childPath.append(child);
				
				/** add to fringe */
				fringe.addElement(childPath);
			
			} // for
			
		} // while

	} // search(UndirectedGraph graph, Heuristics heur, String source, String goal)
		
} // class AStar


